import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Practice2 {


//    136. 只出现一次的数字
//    这里是  硬写  该方法不好 理解set集合
    public int singleNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for(int x: nums) {
            if(hashSet.contains(x)){
                hashSet.remove(x);
            }else {
                hashSet.add(x);
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(hashSet.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }




//    138. 复制带随机指针的链表
//    1、第一次遍历链表，存储老节点和新节点之间的映射关系
//    2、第2次遍历链表，修改新节点的next和random
//    3、return map.get(head);
//    这题得   看图理解
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }


//    771. 宝石与石头
//     给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
//     stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
//     字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
//          思路：宝石放到集合当中 遍历石头就OK了

    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();//引用类型必须是Character 不能是 char
        for (char ch : jewels.toCharArray()) {  //char 和 Character都可以
            set.add(ch);
        }
        int count = 0;
        for (Character ch : stones.toCharArray()) {
            if (set.contains(ch)) {
                count++;
            }
        }
        return count;
    }



//    [编程题]旧键盘
//    旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。
//    现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
    public void func(String beforeStr,String afterStr) {
        HashSet<Character> set = new HashSet<>();
        for (Character ch : afterStr.toUpperCase().toCharArray()) {
            if (!set.contains(ch)) {
                set.add(ch);
            }
        }

        HashSet<Character> set2 = new HashSet<>();
        for (Character ch2 : beforeStr.toUpperCase().toCharArray()) {
            if (!set.contains(ch2) && !set2.contains(ch2)) {
                set2.add(ch2);
                System.out.println(ch2);
            }
        }
    }






//    692. 前K个高频单词  2.19  1:20 建议再看一遍解析
//    给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//    返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

    public static List<String> topKFrequent(String[] words, int k) {
//        1.统计每个单词出现的次数
        HashMap<String,Integer> map = new HashMap<>();
        for (String str : words) {
            if (!map.containsKey(str)){
                map.put(str,1);
            }else {
                int val = map.get(str);
                map.put(str,val+1);
            }
        }

//        2.建立大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

//                频率相同比较 单词顺序
                if (o1.getValue()-o2.getValue() == 0) {
                    return o2.getKey().compareTo(o1.getKey());//大根堆
                }

                return o1.getValue()-o2.getValue();//小根堆
            }
        });

//        3.遍历你的map
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if (minHeap.size() < k){
                minHeap.offer(entry);//重点  当没有放满k个时 offer->siftUp->siftUpUsingComparator->
                // if (comparator.compare(x, (E) e) >= 0) break;     这段语句  x代表o2   (E) e代表o1
//                如果k=3  minHeap内有a-2  那么在加入一个b-2   它们不会进行交换 因为2-2=0 break
//                又因为代码最后 又进行逆置  导致 b-2在前 a-2在后
//                你只进行频率比较 没有考虑频率相同比较key的情况
//                解决：在匿名函数内提供判断条件
            }else {
//                说明堆中 已经放了k个元素 需要看对顶元素的数据和当前数据大小关系
                Map.Entry<String,Integer> top = minHeap.peek();
//                判断频率是否相同 结果相同
                if (top.getValue().compareTo(entry.getValue()) == 0) {
//                    比较单词大小 小的入堆  在minHeap内部悠久实现key比较的大根堆
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }

//                    频率结果不相同  堆顶元素小  则出队  入entry
                }else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

//        因为返回值是List<String>  使用需要创建一个链表
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            list.add(top.getKey());
        }

        Collections.reverse(list);//集合工具类
        return list;
    }

    public static void main(String[] args) {
//        String[] words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        String[] words = {"i","love","leetcode","i","love","coding"};
        List<String> str = new ArrayList<>();
        str = topKFrequent(words,2);
//        System.out.println(str);
    }





}
